from typing import List


class Solution:
    def smallestDistancePair(self, nums: List[int], k: int) -> int:
        nums.sort()
        n = len(nums)

        def f(limit):  # 小于等于limit有多少对
            r = 0
            cnt = 0
            for l in range(n):
                while r < n and nums[r] - nums[l] <= limit:
                    r += 1
                cnt += r - l - 1
            return cnt >= k

        left = 0
        right = nums[-1] - nums[0]
        while left <= right:
            mid = (left + right) >> 1
            if f(mid):
                right = mid - 1
            else:
                left = mid + 1
        return right + 1


if __name__ == '__main__':
    s = Solution()
    r = s.smallestDistancePair([1, 6, 1], k=3)
    print(r)
